A number of systems and programs are offered on the market for the design of parts, assemblies of parts and products thereof, such as the one provided by Dassault Systémes under the trademark CATIA (Computer Aided Three Dimensional Interactive Application). CATIA is a multi-platform CAD/CAM/CAE software suite, commonly referred to as a 3D Product Lifecycle Management (PLM) software suite. It supports multiple stages of product development (CAx), ranging from conceptualization, through design (CAD) and manufacturing (CAM), until analysis (CAE). This software suite is customizable via application programming interfaces (API). Some versions can be adapted in various programming languages, under dedicated APIs.
These so-called CAD systems notably allow a user to construct and manipulate complex three dimensional (3D) models of objects or assemblies of objects. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. These CAD systems manage parts or assemblies of parts as modeled objects, which are mainly specifications of geometry. In particular, CAD files contain specifications, from which geometry is generated. From geometry, a representation is generated. Specifications, geometry and representation may be stored in a single CAD file or multiple ones. CAD systems include graphic tools for representing the modeled objects to the designers; these tools are dedicated to the display of complex objects—the typical size of a file representing an object in a CAD system extending up to the range of a Mega-byte for part, and an assembly may comprise thousands of parts. A CAD system manages models of objects, which are stored in electronic files.
Designing a mechanical part with a known CAD system can be seen as defining the geometrical shape and dimensions of said part so as to fit functional and manufacturing requirements. Mainly, the resulting shape is a combination of basic features such as pad, pocket, groove, shaft etc. created by the designer. Through complex geometrical and topological computations, the CAD system yields the boundary representation of the solid (mechanical part) as e.g. a closed and oriented surface.
One knows the concept of swept volumes, e.g. in the fields of geometric design, machining simulation, robotics, or digital mockup. Given a solid, called “profile” in the following, and a trajectory thereof, we call the swept volume the union of all positions of the profile along the said trajectory. The representation of swept volumes can be used to design shapes, simulate the process of material removal or addition, detect collisions and compute clearance in moving parts and mechanisms. For instance the calculation of a swept volume is useful to determine the required space of a vehicle motor that is vibrating during its functioning. Also, the calculation of a swept volume is useful to determine the required space of a wheel of a vehicle while said wheel turns left and right and moves up and down thanks to shock absorbers. Also, the swept volume is useful to determine the required space of a manufacturing tool.
In this respect, one may rely on Minkowski sums or additions. An efficient computation of Minkowski sums may be used to compute large offsets and machining trajectories or repair polyhedral models.
Owing to the importance of swept volumes in geometric modeling, many solutions have been developed to represent the said swept volumes both in academic works and commercial applications.
A naive approach (hereafter referred to as method “M1”) consists in considering the union of a finite number of instances of the profile volume along its trajectory.
A more elaborate method (hereafter “M2”), which has a number of variants, consists in decomposing a given solid or profile in convex parts, then producing the convex bodies resulting of the sweeping of each convex part by each segment of a piecewise linear trajectory, then take the union of all theses convex bodies (see e.g. “Accurate Minkowski sum approximation of polyhedral models”, Gokul Varadhan, Dinesh Manocha, Graphical Models 68 (2006) 343-355, Video mode of MachineWorks uses this approach).
Another class of methods (“M3”) consists in computing a superset of the boundary of the swept volume by considering all the pairs (profile triangle, trajectory point) or (profile edge, trajectory edge) that could, according to local geometry only, appear in the swept volume boundary. These methods produce a non structured set of triangles (a triangle “soup”) whose union is, in theory, a subset of the swept volume and a superset of the swept volume boundary (see e.g. U.S. Pat. No. 6,993,461, in the name of Applicants).
A mathematically well founded method (“M4”) known as “kinetic convolution” has been developed for two-dimensional (2D) swept body computation (see e.g. L. J. Guibas, M. Overmars, and J. Stolfi. A kinetic framework for computational geometry.
In proc. 24th Annu IEEE Sympos. Found. Comput. Sci, pages 100-11, 1983). This method produces a 2D closed piecewise linear curve. This pioneer work as since given rise to several 2D implementations such as described in:
Ron Wein, Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method ACS Technical Report No.: ACS-TR-241300-04; and
Victor Milenkovic, Elisha Sacks: An approximate arrangement algorithm for semi-algebraic curves. Symposium on Computational Geometry 2006: 237-246.
On the other hand, other works extend the line of 2D work to 3D polyhedral solids. A main result is a procedure that, given two solids whose boundary is a polyhedral 2-manifold, computes a so called “polyhedral tracing”, see e.g.:
J. Basch, L. J. Guibas, G. D. Ramkumar and L. Ramshaw, Polyhedral tracings and their convolution. In Proc. 2nd Workshop on Algorithmic Foundations of Robotics, 1996; and
G. D. Ramkumar: “Tracings and their convolution: theory and applications”, PhD. thesis (1998), Stanford, and related subsequent papers.
One knows two ways of implementing methods (M1), (M2), (M3) and (M4) in practice. For example methods (M1) and (M2) produce a set of solids whose union is the result. Similarly, method (M3) produces a set of triangles. Computing in practice an explicit representation of the union at issue is not mandatory. It is even problematic for 3D complex geometries because it is extremely sensitive to rounding errors.
Another class of methods relies on voxel or dexel volume representations (“M5”, cf. the “Photo mode” in “MachineWorks”).
Next, the so-called “wrapping methods” (“M6”) produce a watertight, rough approximation of the swept solid. It is fast and robust but it is not accurate. The technology is for instance described in “Swept volume approximation of a polygon soup”, J. C. Himmelstein, E. Ferré, J. P. Laumond, International Conference on Robotics and Automation, 10-14 Apr. 2007, Roma, pp 4854-4860. It is implemented in “Kineo path planner” product of “Kineo Computer Aided Motion” company. This method amounts to compute an implicit representation of the swept volume by calculating the distance to the swept surface boundary on the vertices of a 3D regular grid. This distance field is computed from a sampling of the trajectory satisfying a given 3D tolerance on the resulting sweep. Then the outer skin is collected using a variant of a classical algorithm, known as the “marching cube”.
Finally, a number of patents or patent applications broadly deals with the subject, see e.g. U.S. Pat. Nos. 7,091,995, 7,031,790, 6,690,385, 5,649,084, 6,307,555, 6,989,830, 6,988,121, EP-A-0 280 968, EP-A-0 405 106, EP-A-0 280 968, U.S. Pat. No. 5,159,512, US 2003/014133, US 2005/143963, and US 2004/059450.
The methods M1-M6 evoked above are not infallible.
For example, method (M1) requires considering a large number of instances of the swept volume and is therefore very expensive in memory and computation time if one asks for a good accuracy.
Method (M2) presents the same drawbacks as method (M1), yet in a lesser extent. For each segment of the trajectory and each convex part of the profile, it generates a body of roughly the same complexity (i.e. number of triangles) than the convex part.
Method (M3) is efficient in a number of respects. For example the number of produced triangles is of the order of magnitude of the number of triangles effectively produced in the result when the trajectory does not “wind” too much. A major drawback of this method is that it is sensitive with respect to rounding errors: an arbitrarily small perturbation in the vertices coordinates may create small gaps in the boundary of the result. Typically it is quite easy to produce the set of triangles. However, it is in general not possible to extract a topologically valid watertight polyhedron, due to robustness issues. Another limitation of (M3) is that it is restricted to one dimensional trajectory, which is not relevant to compute Minkowski sums.
An obvious drawback of the 2-dimensional version of method (M4) is that it is restricted to 2D polygons. In addition, the theoretical approach chosen here induces significant limitations. Firstly, it is intrinsically limited to Minkowski sum. In particular, path planning, robotics or machining applications of these procedures are restricted to translational motions (meaning that only 3 axis machining is possible). Secondly, the operands of the Minkowski sum have to be solids whose boundaries are polyhedral 2-manifolds with all their vertices satisfying the so called “hemisphere assumption”: for each vertex V, the set of outward normal vectors to faces adjacent to V has to be included in a hemisphere. Now, there are numerous examples of a manifold vertex violating the hemisphere assumption. Finally, another drawback is that, as far as known by the present inventors, this 3D procedure has not been implemented basically.
Method (M5) is efficient and robust but the size of data increases dramatically with the desired accuracy. It is then a good method for applications where the accuracy is not critical.
Method (M6) produces a conservative approximation well suited to rough collision analysis but it is not accurate enough for machining simulations. Furthermore, the theoretical drawback is that the cost in time and memory increases as O(1/ε3) where ε is the required accuracy, while a theoretical increase rate of O(1/ε) would be preferred. Indeed, in practice, method (M6) is fast if the relative accuracy (the ratio between the model size and the required accuracy) is small. The examples mentioned in the paper make use of grids whose sizes range from 323 to 1283 voxels which leads respectively to the values 64 to 256 for the relative accuracy. This accuracy may be enough for rough path planning or collision detection or as a first fast rejection step. However manufacturing applications need relative accuracies which, typically, range from 103 to 105.
To summarize the above analysis, the prior art shows too much sensitivity with respect to rounding errors, is expensive either in memory or in computation cost, and/or is not accurate enough, at least for some applications. Accordingly, there remains a need for a robust (topologically correct and watertight) and accurate method of computing a swept volume (more generally a boundary of a modeled object), the method compatible with a large class of objects.